# 两数之和： https://leetcode-cn.com/problems/two-sum/submissions/

class Solution:
    def twoSum(self, nums: list, target: int) -> list:
        """ 
            暴力解法优化，每次都是线性查找 j， 使用hash表保存值，O(1) 查找
            个人觉得，hash 查找还是不好想的， 因为 可能存在重复的元素， 那么 字典的键冲突，对应的 索引值就被更新掉了
            尽管之前做过这题， 现在自己又去想了一下，还是没想到如何写（或者是自己没说服自己，hash的思路）
            看了答案解析，恍然大悟！ 我们可以先将元素与 字典中的 target进行比较，然后再插入该元素到 字典。
            问题是： 如果 target - num 再 当前的num 后面，那还没加入到字典里呢？ 不是错过答案了吗？ 
            要知道，当遍历到 target - num 时，   target - (target - num) 不是正好再 字典里吗？ 完全正确。
        """
        hashMap = {}
        for i, num in enumerate(nums):
            if target - num in hashMap:
                return [i, hashMap.get(target - num)]
            hashMap[num] = i
        
        return []

